﻿'''
题目描述
单词接龙的规则是：
可用于接龙的单词首字母必须要前一个单词的尾字母相同；
当存在多个首字母相同的单词时，取长度最长的单词，如果长度也相等，则取字典序最小的单词；已经参与接龙的单词不能重复使用。
现给定一组全部由小写字母组成单词数组，并指定其中的一个单词作为起始单词，进行单词接龙，
请输出最长的单词串，单词串是单词拼接而成，中间没有空格。
输入描述
输入的第一行为一个非负整数，表示起始单词在数组中的索引K，0 <= K < N ；
输入的第二行为一个非负整数，表示单词的个数N；
接下来的N行，分别表示单词数组中的单词。
备注：
单词个数N的取值范围为[1, 20]；
单个单词的长度的取值范围为[1, 30]；
输出描述
输出一个字符串，表示最终拼接的单词串。
示例1
输入
0
6
word
dd
da
dc
dword
d
输出
worddwordda
说明
先确定起始单词word，再接以d开头的且长度最长的单词dword，剩余以d开头且长度最长的有dd、da、dc，则取字典序最小的da，所以
最后输出worddwordda。
示例2
输入
4
6
word
dd
da
dc
dword
d
输出
dwordda
说明
先确定起始单词dword，剩余以d开头且长度最长的有dd、da、dc，则取字典序最小的da，所以最后输出dwordda。
解题思路
接龙规则：
下一个接龙的单词必须以前一个单词的尾字母开头。
当有多个符合条件的单词时：
优先选择长度最长的单词；
如果长度相等，选择字典序最小的单词。
已经使用的单词不能重复使用。
解题步骤
确定起始单词：从输入的 K 索引中找到起始单词。
根据接龙规则选择后续单词：
选择以当前单词尾字母开头的单词。
先选长度最长的单词；若长度相等，选字典序最小的单词。
将这个单词接到当前的结果串中，重复这个过程，直到没有可以接龙的单词为止。
输出结果：将最终拼接的单词串输出。
'''
#输入描述：
#输入的第一行为一个非负整数，表示起始单词在数组中的索引K，0 <= K < N ；
#输入的第二行为一个非负整数，表示单词的个数N；
#接下来的N行，分别表示单词数组中的单词。
#输出描述：输出一个字符串，表示最终拼接的单词串。

#定义一个方法返回给定单词列表和前缀字符的下一个接龙单词

def next_word(word_arr,pre_char):
    #定义字典，存储以给定字符为key的单词列表
    word_dict = {}
    for words in word_arr:
        first_char = words[0]
        tmp_list = word_dict.get(first_char,[]) #get()找到返回列表，否则返回默认值
        tmp_list.append(words)   #增加当前word
        word_dict[first_char] = tmp_list
    #查找以给定字符为首字符的最长word和字典序最小word(如多个长度最大且相等)
    max_length = 0
    min_word = ""
    
    #注意字典如无当前key则返回none则无法使用len()判断长度,所以需要指定默认值空list []
    pre_char_list = word_dict.get(pre_char,[])  
    
    if len(pre_char_list)!=0:
        for word in pre_char_list:
            if len(word) > max_length or (len(word) == max_length and word < min_word):
                max_length = len(word)
                min_word = word
    return min_word

if __name__ == '__main__':
    #读取第一行输入
    k = int(input())
    #读取第二行输入
    n = int(input())
    #读取n行单词
    word_list = []
    for i in range(n):
        word_list.append(input())

    #添加开始word到result
    result = []
    result.append(word_list[k])
    start_word = word_list[k]
    word_list.remove(start_word)  #移除添加到结果的word
    #查找下一个
    find_next_word = next_word(word_list,start_word[-1])
    while find_next_word != "":
        result.append(find_next_word)
        word_list.remove(find_next_word)
        find_next_word = next_word(word_list,find_next_word[-1])
    #输出结果
    print(''.join(result))

